package problem45;

//45.跳跃游戏2
//https://leetcode.cn/problems/jump-game-ii/

class Solution {
    public int jump(int[] nums) {
        int left = 0, right = 0;
        int ret = 1;
        int n = nums.length;
        if(n == 1) return 0;
        while(true) {
            int x = 0, y = 0;
            for(int i = left; i<=right && i<n; i++) {
                x = i + 1;
                y = Math.max(y, i + nums[i]);
            }
            left = x;
            right = y;
            if(right >= n-1) break;
            ret ++;
        }
        return ret;
    }
}